/**
 * | -------------------------------------------------- |
 * |        Universidad Del Valle De Guatemala          |
 * | -------------------------------------------------- |
 * | Algoritmos y Estructuras de Datos.                 |
 * | Sección 20.                                        |
 * | Diego Bran, Eduardo Drummond, Javier García,       |
 * | Derek Orbaugh, Miguel Zea.                         |
 * | Hoja de Trabajo #3.                                |
 * | 27/07/2012.                                        |
 * | Descripción: implementación de un programa que     |
 * | evalúe el desempeño de distintos algoritmos de     |
 * | ordenamiento, sobre un arreglo de enteros de hasta |
 * | 2000 elementos.                                    |
 * | -------------------------------------------------- |
 */
package sort;

/**
 * Clase que recopila los 5 métodos sort implementados, con el fin de
 * unificar el trabajo y las pruebas unitarias.
 */
public class Sorter {
    
    /**
     * Pre: ninguna
     * Post: el arreglo de enteros data es ordenado ascendentemente.
     */
    public static void selectionSort(int[] data) {
        for (int i = 0; i < data.length; i++) {
            for (int j = i + 1; j < data.length; j++) {
                if (data[i] > data[j]) {
                    int temp = data[j];
                    data[j] = data[i];
                    data[i] = temp;
                }
            }
        }
    }
    
    /**
     * Pre: ninguna.
     * Post: el arreglo de enteros data es ordenado ascendentemente.
     */
    public static void insertionSort(int[] data) {
        int i = 0, j = 0;
        for (i = 0; i < data.length; i++) {
            int temp = data[i];
            
            for (j = i; j > 0; j--) {
                if (temp < data[j - 1]) {
                    data[j] = data[j - 1];
                } else {
                    break;
                }
            }
            data[j] = temp; 
        }
    }
    
    /**
     * Pre: ninguna.
     * Post: el arreglo de enteros data es ordenado ascendentemente.
     */
    public static void bubbleSort(int[] data) {
        for (int i = 0; i < data.length; i++) {
            for (int j = 1; j < data.length; j++) {
                if (data[j] < data[j - 1] ) {
                    int temp = data[j];
                    data[j] = data[j - 1];
                    data[j - 1] = temp;            
                }
            }
        }
    }
    
    /**
     * Los algoritmos de mergesort y quicksort fueron tomados del libro Java
     * Structures de Duane Bailey, capítulo 6.
     */
    
    /**
     * Pre: ninguna.
     * Post: el arreglo de enteros data es ordenado ascendentemente.
     */
    public static void mergeSort(int[] data) {
        mergeSortRecursive(data, new int[data.length], 0, data.length - 1);
    }
    
    /** 
     * Pre: data[middle..high] y temp[low..middle-1] son ascendentes.
     * Post: data[low..high] contiene todos los valores en orden ascendente.
     */
    private static void merge(int data[], int temp[], int low, int middle, int high) {
        int ri = low; 
        int ti = low; 
        int di = middle; 
        
        while (ti < middle && di <= high) {
            if (data[di] < temp[ti]) {
                data[ri++] = data[di++]; 
            } else {
                data[ri++] = temp[ti++]; 
            }
        }
        
        while (ti < middle) {
            data[ri++] = temp[ti++];
        }
    }

    /**
     * Pre: 0 <= low <= high < data.length.
     * Post: los valores en data[low..high] están en orden ascendente.
     */
    private static void mergeSortRecursive(int data[], int temp[], int low, int high) {
        int n = high - low + 1;
        int middle = low + n/2;
        int i;
        if (n < 2) return;
        
        for (i = low; i < middle; i++) {
            temp[i] = data[i];
        }
        
        mergeSortRecursive(temp, data, low, middle - 1);
        mergeSortRecursive(data, temp, middle, high);
        merge(data, temp, low, middle, high);
    }
    
    /**
     * Pre: ninguna.
     * Post: el arreglo de enteros data es ordenado ascendentemente
     */
    public static void quickSort(int[] data) {
        quickSortRecursive(data, 0, data.length - 1);
    }
    
    /** 
     * Pre: 0 <= i,j < data.length.
     * Post: se intercambian data[i] y data[j].
     */
    private static void swap(int data[], int i, int j) {
        int temp;
        temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
    
    /**
     * Pre: left <= right.
     * Post: data[left] es colocado en la posición(retornada) correcta.
     */
    private static int partition(int data[], int left, int right) {
        while (true) {
            while (left < right && data[left] < data[right]) right--;
            
            if (left < right) swap(data,left++,right);
            else return left;

            while (left < right && data[left] < data[right]) left++;
            
            if (left < right) swap(data,left,right--);
            else return right;
        }
    }
    
    /** 
     * Pre: left <= right.
     * Post: data[left..right] en orden ascendente.
     */ 
    private static void quickSortRecursive(int data[], int left, int right) {
        int pivot; 
        if (left >= right) return;
        pivot = partition(data,left,right); 
        quickSortRecursive(data,left,pivot-1); 
        quickSortRecursive(data,pivot+1,right);
    }
}
